﻿//2594. 修车的最少时间
//给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
//同时给你一个整数 cars ，表示总共需要修理的汽车数目。
//请你返回修理所有汽车 最少 需要多少时间。
//注意：所有机械工可以同时修理汽车。

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars)
    {
        auto check = [&](long long t)->bool
        {
            int sum = 0;
            for (auto e : ranks)
            {
                // e*x*x=t;
                sum += sqrt(t / e);
                if (sum >= cars)
                    return true;
            }
            return false;
        };
        int x = ranges::min(ranks);
        int n = ranks.size();
        long long left = 1, right = 1LL * x * cars * cars;
        while (left <= right)
        {
            long long mid = left + (right - left) / 2;
            if (check(mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        return right + 1;
    }
};